package pack;

import java.util.Hashtable;



/*******************************************************************
 * Computing the exact alignment of three sequences with sum-of-pairs-score.
 * Input arguments are three sequences, a score matrix and gap costs.
 * 
 * Running time O(n^k*2^k), where n is length of sequence and k is amount of sequences.
 * Space Consumption O(n^k*2^k)	
 * 
 * @author Paula C. Tataru, Marcus Schroeder
 *
 *****************************************************************/


public class ExactMsaThreeSequences {

	/******************************************************************
	 *  Default constructor
	 *  Computes alignment of hardcoded sequences
	 *****************************************************************/
	public ExactMsaThreeSequences(Hashtable<String,Hashtable<String,String>> scoreMatrix,int gapcost) {		
		
		
		this.scoreMatrix = scoreMatrix;		
		this.gapcost = gapcost;		
		
		startAlignment();
		
	}
	
	
	
	/******************************************************************
	 * Alternative constructor
	 * Computes alignment of three given sequences and a given score matrix
	 *****************************************************************/
	public ExactMsaThreeSequences(String s1, String s2, String s3,Hashtable<String,Hashtable<String,String>> scoreMatrix,int gapcost) {
		
		this.s1 = s1;
		this.s2 = s2;
		this.s3 = s3;
		
		
		this.scoreMatrix = scoreMatrix;		
		this.gapcost = gapcost;		
		
		startAlignment();
		
	}	
	
	
	
	
	/******************************************************************
	 * Alternative constructor
	 * Sequences are handed over in an array s
	 *****************************************************************/
	public ExactMsaThreeSequences(String[] s, Hashtable<String,Hashtable<String,String>> scoreMatrix,int gapcost) {
		
		this.s1 = s[0];
		this.s2 = s[1];
		this.s3 = s[2];
		
		
		
		this.scoreMatrix = scoreMatrix;		
		this.gapcost = gapcost;
		
		startAlignment();
	}
	
	
	/*****************************************************************
	 * GLOBALS
	 *****************************************************************/
	
	// The three sequences	
	private String s1 = "aaacccaaa";
	private String s2 = "cccaaa";
	private String s3 = "aaaccc";
	
	private String as1 ="";
	private String as2 ="";
	private String as3 ="";
	
	private int costs = 0; 
	
	/*****************************************************************
	 * GETTERS
	 *****************************************************************/
	public int getValueInAlignmentMatrix(int i, int j,int k) {		
		return D[i][j][k];
	}
	
	public double getTime(){return end_time;}
	public int getCosts(){return costs;}
		
	/******************************************************************
	 *  Gapcosts
	 *****************************************************************/
	private int gapcost = -5;
	
	
	private double end_time = 0;
	
	/******************************************************************
	 *  The Score Matrix
	 *****************************************************************/
	private Hashtable<String,Hashtable<String,String>> scoreMatrix;
	
	
	
	
	
public void startAlignment(){
		
		double time = System.nanoTime();
		D =  new int[s1.length()+1][s2.length()+1][s3.length()+1];
		
		computeExactAlignment();		
		
		costs = D[s1.length()][s2.length()][s3.length()];
		
		//traceback(s1.length(),s2.length(),s3.length());	
		
		
		end_time = (System.nanoTime()-time)/1000000000;
		
		
		as1 = new StringBuffer(as1).reverse().toString();
		as2 = new StringBuffer(as2).reverse().toString();
		as3 = new StringBuffer(as3).reverse().toString();		
		
	}

	public void printOutput(){
		System.out.println("--------------------------------------");
		System.out.println("Results:");
		System.out.println("--------------------------------------");
		System.out.println("Sequence lengths: "+s1.length()+", "+s2.length()+", "+s3.length());
		System.out.println("Taken time in s: "+end_time);
		System.out.println("Score: "+costs);
		System.out.println("--------------------------------------");
		System.out.println();
		System.out.println();
		System.out.println(as1);
		System.out.println(as2);
		System.out.println(as3);
		System.out.println();
	}
	
	/******************************************************************
	 *  Alignment Matrix D
	 *  
	 *  Has three dimensions with size [n,m,o], where 
	 *  			n is length of sequence 1,
	 *  			m is length of sequence 2,
	 *  			o is length of sequence 3,
	 *  
	 *  Is intialized in complete size (n*m*o) on class initialization.
	 *****************************************************************/
	private int[][][] D; 
	
	
	
	/******************************************************************
	 * Returns the score for two compared characters a and b
	 * Values stems from a score matrix 
	 *****************************************************************/
	private int matchScore(char a,char b){		
		
		String score = ((Hashtable<String,String>) scoreMatrix.get(""+a)).get(""+b).toString();

		return Integer.parseInt(score);
		
		//return Float.parseFloat(score);		
		
	}
	
	
	/******************************************************************
	 * Compute exact alignment of three sequences.
	 *****************************************************************/	
	private void computeExactAlignment(){
		
		int n = s1.length();
		int m = s2.length();
		int o = s3.length();
		
		
		
		/******************************************************
		 *  INTIALIZING THE ALIGNMENT MATRIX
		 ******************************************************/
		D[0][0][0] = 0;
		
				
		// D_s1_s2
		PairwiseGlobalAlignment d_sub = new PairwiseGlobalAlignment(scoreMatrix, s1, s2, gapcost);
		
		for(int i = 0; i <= n; i++){			
			for(int j = 0; j <= m; j++){
				
				D[i][j][0] = d_sub.getValueInAlignmentMatrix(i, j) + (i+j)*gapcost;
				
			}
		}
		
				
		// D_s1_s3		
		d_sub = new PairwiseGlobalAlignment(scoreMatrix, s1, s3, gapcost);
		
		for(int i = 0; i <= n; i++){			
			for(int k = 0; k <= o; k++){
				
				D[i][0][k] = d_sub.getValueInAlignmentMatrix(i, k) + (i+k)*gapcost;
				
			}
		}
		
		// D_s2_s3		
		d_sub = new PairwiseGlobalAlignment(scoreMatrix, s2, s3, gapcost);
			
		for(int j = 0; j <= m; j++){			
			for(int k = 0; k <= o; k++){
				
				D[0][j][k] = d_sub.getValueInAlignmentMatrix(j, k) + (j+k)*gapcost;
				
			}
		}
			

		/******************************************************
		 *  FILLING THE TABLE	
		 ******************************************************/
		
		for(int i = 1; i <= n; i++){			
			for(int j = 1; j <= m; j++){				
				for(int k = 1; k <= o; k++){
					
					
					int c_ij = matchScore(s1.charAt(i-1), s2.charAt(j-1));
					int c_ik = matchScore(s1.charAt(i-1), s3.charAt(k-1));
					int c_jk = matchScore(s2.charAt(j-1), s3.charAt(k-1));
					
					int d1 = D[i-1][j-1][k-1] + c_ij + c_ik + c_jk;
					int d2 = D[i-1][j-1][k] + c_ij + 2*gapcost;					
					int d3 = D[i-1][j][k-1] + c_ik + 2*gapcost;
					int d4 = D[i][j-1][k-1] + c_jk + 2*gapcost;					
					int d5 = D[i-1][j][k] + 2*gapcost;
					int d6 = D[i][j-1][k] + 2*gapcost;					
					int d7 = D[i][j][k-1] + 2*gapcost;
					
					
					/** FINDING THE MINIMUM ENTRY **/
					D[i][j][k] = Math.min(
										Math.min(
												Math.min(d1, d2),
												Math.min(d3, d4)
										),
										Math.min(
												Math.min(d5,d6),
												d7
										)
								);		
					
				}
				
			}
			
		}
	}
	

	private void traceback(int i, int j, int k){
		
		
		
		if(i == 0 && j == 0 && k == 0){
			
		}
		else{
			int c_ij = 0;
			int c_ik = 0;
			int c_jk = 0;			
			
			if(i>0 && j >0) c_ij = matchScore(s1.charAt(i-1), s2.charAt(j-1));
			if(i>0 && k >0) c_ik = matchScore(s1.charAt(i-1), s3.charAt(k-1));
			if(k>0 && j >0) c_jk = matchScore(s2.charAt(j-1), s3.charAt(k-1));
			
			if((i>0 && j>0 && k>0) && D[i][j][k] == D[i-1][j-1][k-1] + c_ij + c_ik + c_jk){				
					
					as1 = as1+s1.charAt(i-1);
					as2 = as2+s2.charAt(j-1);
					as3 = as3+s3.charAt(k-1);
					
		
					traceback(i-1,j-1,k-1);					
				
			}
			else if((i>0 && j>0) && D[i][j][k] == D[i-1][j-1][k] + c_ij + 2*gapcost){
					
					as1 = as1+s1.charAt(i-1);
					as2 = as2+s2.charAt(j-1);
					as3 = as3+"-";
		
					traceback(i-1,j-1,k);				
			}
			else if((i>0 && k>0) && D[i][j][k] == D[i-1][j][k-1] + c_ik + 2*gapcost){
					
					as1 = as1+s1.charAt(i-1);
					as2 = as2+"-";
					as3 = as3+s3.charAt(k-1);
					
					traceback(i-1,j,k-1);
			}
			else if((j>0 && k>0) && D[i][j][k] == D[i][j-1][k-1] + c_jk + 2*gapcost){
					
					as1 = as1+"-";
					as2 = as2+s2.charAt(j-1);
					as3 = as3+s3.charAt(k-1);
					
					traceback(i,j-1,k-1);
				}
			else if(i>0 && D[i][j][k] == D[i-1][j][k] + 2*gapcost){
					
					as1 = as1+s1.charAt(i-1);
					as2 = as2+"-";
					as3 = as3+"-";
					
					traceback(i-1,j,k);
			}
			else if(j > 0 && D[i][j][k] == D[i][j-1][k] + 2*gapcost){
					
					as1 = as1+"-";
					as2 = as2+s2.charAt(j-1);
					as3 = as3+"-";
					
					traceback(i,j-1,k);
			}
			else if( k > 0 && D[i][j][k] == D[i][j][k-1] + 2*gapcost){
					
					as1 = as1+"-";
					as2 = as2+"-";
					as3 = as3+s3.charAt(k-1);
					
					traceback(i,j,k-1);
			}
		}
		
		
	}



	
		
}
